FAQ + Errata (Assignment 1)

Because we don't require your functions to maintain minimality, there are several well-formed tries that can represent the same dictionary. For example, both Trie False [] and Trie False [('a',Trie False [])] represent the empty dictionary.

For this reason, your Monoid TrieMonoid instance might not satisfy the monad laws. Instead, we only require you to satisfy the monad laws up-to dictionary equivalence.

We say that two well-formed dictionaries \(t\) and \(t'\) are dictionary equivalent, written \(t \simeq t'\), if \(\forall \mathit{xs}. \mathtt{check}\ t\ \mathit{xs} = \mathtt{check}\ t'\ \mathit{xs}\). TrieMonoid only needs to satisfy the following laws:

In the lecture, this was phrased as "identity up-to pruning", but that amounts to the same thing.

The comment above the definition of pick in the code template has the argument order backwards. The type signature is the argument order you should go with. Thus, whenever the comment says pick x xs, pretend it says pick xs x.

Here is a debugged comment:

{- pick xs x is a utility function which should satisfy the following
   properties:

   - If `elem x xs`, then `pick xs x = (True,ys)` for some `ys`
                     such that `xs` is a permutation of `x:ys`.
   - If `not(elem x xs)`, then `pick xs x = (False,ys)`, for some `ys`
                          such that `xs` is a permutation of `ys`.

   This utility function is useful for pulling out specific tiles from
   a rack.
 -}
pick :: Eq a => [a] -> a -> (Bool,[a])
pick = error "TODO: implement pick"

No. The dictionary can contain any Char. The default generator only generates characters in the [a..z] range for simplicity, but you should not depend on this behaviour.

If the dictionary happens to contain both lower-case and upper-case characters, these should be treated as distinct letters. (For practical purposes, the user of your program probably wants to ensure that their dictionary has normalised case. But that's not your responsibility: you should treat distinct characters as distinct.)

No. If they touch pre-existing letters, legal words need to be formed. But they do not have to touch. So for example, on the dog board from the spec, a three-letter word could be a legal move.

Note that while the rules of Scrabble only allow moves that either start at the origin or touch pre-existing words, it is not the responsibility of moves or allMoves to enforce this rule. In a full implementation, you would iterate allMoves over every legal position from which to start a move; this iteration should be responsible for excluding invalid starting points.

The assignment spec mentions an important constraint on the set of legal moves that is not in the inline code comments: that moves need to form a word of length >= 2 in the direction of play, and only newly formed words of length >= 2 need to be legal. A word counts as formed if it includes at least one newly placed tile (at least one blue tile in the pictures).

This implies that moves and allMoves should never return words of length 0 or 1.

On the other hand, filterPlayables should return words of length 0 or 1 when applicable. filterPlayables should only consider which words can be formed using the tiles on the given Rack, and not take other constraints arising from the game rules into consideration.

The bonus marks are 2/100 marks for the final exam.

Obviously, a trie contains a list of subtries, and you need to process that list somehow; iterating through this list is of course allowed. What you shouldn't do is representing dictionaries as lists of strings.

A previous version of the spec claimed that in order for "nastier" to be a legal move, "dog" needs to be one. It should have said "or". Only newly formed words—or in the pictures, words containing at least one blue tile—should be considered.

You're allowed to import additional functions from the libraries already imported by the template, and anything else from base or quickcheck. Or in other words, as long as you can import it without adding stuff to the .cabal file you can import it.

There is no special consideration of Blanks that are already on the board that you need to implement. Once a blank tile is on the board, it is permanently treated as whatever letter the player declared them to be as part of their move, except for scoring purposes. But we don't consider scoring in this assignment so we don't need to make any such distinction.

From top to bottom. So for example, in order to check whether "proof" is a legal move on this board:

bed_board :: Board
bed_board =
  Board
    [(("beds","read"),Nothing),
     (("",""),Nothing),
     (("",""),Nothing),
     (("",""),Nothing),
     (("",""),Nothing),
     (("",""),Nothing),
     (("",""),Nothing),
     (("",""),Nothing)
    ]

…the dictionary would have to contain both "proof" and "bedspread", not "sdebpread".

The shrinker for tries in the assignment is a bit aggressive and tries arguably too many things. Try one of these Arbitrary instances instead:

instance Arbitrary Trie where
  arbitrary = sized $ genTrie . min 15
  shrink (Trie b ts) =
    Trie b <$> shrinkList (\(x,t) -> curry id x <$> shrink t) ts' where
    ts' = zip ['a'..'z'] $ snd <$> ts

instance Arbitrary Trie where
  arbitrary = sized $ genTrie . min 15
  shrink (Trie b ts) =
    Trie b <$> shrinkList (\(x,t) -> curry id x <$> shrink t) ts

instance Arbitrary Trie where
  arbitrary = sized $ genTrie . min 15
  shrink (Trie b ts) = []

If you have a better shrinker, please feel free to share on the forums!